package org.moriraaca.google.interview;

public class StringUnion {
	// time O(N^2)
	public String f1(String a, String b) {
		StringBuilder sb = new StringBuilder();
		
		mainLoop:
		for (int i = 0; i < a.length(); i++) {
			for (int j = 0; j < sb.length(); j++) {
				if (a.charAt(i) == sb.charAt(j)) {
					continue mainLoop;
				}
			}
			
			boolean found = false;
			for (int j = 0; j < b.length(); j++) {
				if (a.charAt(i) == b.charAt(j)) {
					found = true;
					break;
				}
			}
			
			if (found) {
				sb.append(a.charAt(i));
			}
		}
		return sb.toString();
	}
	
	// time O(N)
	public String f2(String a, String b) {
		StringBuilder sb = new StringBuilder();
		boolean [] bSet = new boolean['z' - 'a' + 1];
		
		for (int i = 0; i < b.length(); i++) {
			bSet[b.charAt(i) - 'a'] = true;
		}
		
		for (int i = 0; i < a.length(); i++) {
			if (bSet[a.charAt(i) - 'a']) {
				sb.append(a.charAt(i));
				bSet[a.charAt(i) - 'a'] = false;
			}
		}
		
		return sb.toString();
	}
}
